/*
 * File: population.c
 *
 * Integrantes:
 * @author Jormar Arellano   (05-37840) <jormar.arellano@gmail.com>
 * @author Sabrina Fernández (05-38163) <sabrinamfm@gmail.com>
 */

#include "arraylist.h"
#include "graph.h"
#include "util.h"
#include "population.h"
#include "LocalSearch.h"

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <limits.h>
#include <float.h>

/* * * * * * * * * * * * * * * * * *
 * Funciones de cromosomas
 * * * * * * * * * * * * * * * * * */
Chromosome *newChromosome() {
	Chromosome *chrom = (Chromosome *) malloc(sizeof(Chromosome));

	chrom-> used = 0;
	chrom-> rank = 0.0;
	chrom-> colors = arraylist_new(0);

	return chrom;
}

Chromosome *cloneChromosome(const Chromosome *chrom) {
	int i;
	Chromosome *chrom2 = newChromosome();
	chrom2-> rank = chrom-> rank;
	chrom2-> colors = arraylist_new(chrom-> colors-> length);

	for (i=0; i< chrom-> colors-> length; i++) {
		arraylist_append(chrom2-> colors, chrom-> colors-> data[i]);
	}
	return chrom2;
}

void freeChromosome(Chromosome *chrom) {
	int i;

	if (chrom != NULL) {
		for (i=0; i< chrom-> colors-> length; i++) {
			free(chrom-> colors-> data[i]);
		}
		arraylist_free(chrom-> colors);
		free(chrom);
	}
}

void printChromosome(Chromosome *chrom) {
	int i;
	
	printf("Asignacion: %d, clasificacion: %e\n", chrom->used, chrom->rank);
	printf("Con colores: \n");
	for (i=0; i<chrom-> colors-> length; i++){
		printf(" %d ", *(int *)chrom-> colors-> data[i]);
	}
	printf("\n");
}

ArrayList *newChromosomeArray(int n) {
	int i, *value;
	ArrayList *list = arraylist_new(n);

	for(i=0; i<n; i++) {
		value = malloc(sizeof(int));
		*value = rand()%n + 1;
		arraylist_append(list, value);
	}
	return list;
}

/* * * * * * * * * * * * * * * * * *
 * Funciones de poblacion 
 * * * * * * * * * * * * * * * * * */
Population *newPopulation(int n) {
	Population *pop = (Population *) malloc(sizeof(Population));

	pop-> better = newChromosome();
	pop-> chrom = arraylist_new(n);
	return pop;
}

Population *clonePopulation(Population *pop) {
	int i;
	Chromosome *chrom;
	Population *ret = newPopulation(pop-> chrom-> length);

	// Copiamos el mejor vertice.
	chrom = cloneChromosome(pop-> better);
	ret-> better = chrom;

	// Agregamos todos los cromosomas.
	for(i=0; i < pop-> chrom-> length; i++){
		chrom = pop-> chrom-> data[i];
		arraylist_append(ret-> chrom, chrom);
	}
	
	return ret;
}

void freePopulation(Population *pop) {
	int i;
	if (pop != NULL) {
		freeChromosome(pop-> better);
		for (i=0; i< pop-> chrom-> length; i++) {
			freeChromosome(pop-> chrom-> data[i]);
		}
		arraylist_free(pop-> chrom);
		free(pop);
	}
}

void printPopulation(Population *pop) {
	int i;
	
	printf("Poblacion con un mejor cromosoma:\n");
	printChromosome(pop->better);
	printf("Donde todos los cromosomas son: \n");
	for (i=0; i<pop-> chrom-> length; i++) {
		printChromosome((Chromosome *)(pop-> chrom-> data[i]));
	}
	printf("\n");
}

void printChromList(ArrayList *list) {
	int i;
	
	printf("Donde todos los cromosomas son: \n");
	for (i=0; i<list-> length; i++) {
		printChromosome((Chromosome *)(list-> data[i]));
	}
	printf("\n");
}

Chromosome *findBetter(Population *pop) {
	int i;
	double max = DBL_MAX;
	Chromosome *chrom, *ret = newChromosome();

	for(i=0; i < pop-> chrom-> length; i++) {
		chrom = newChromosome();
		chrom = pop-> chrom-> data[i];
		if ( (chrom-> rank) < max) {
			max = chrom-> rank;
			ret = cloneChromosome(pop-> chrom-> data[i]);
		}
	}

	return ret;
}

ArrayList *crossoverOnePoint (ArrayList *list, int firstPoint) {
	int i = 0,j; 
	ArrayListValue aux;
	Chromosome	*chrom1, *chrom2;
	ArrayList *cross = arraylist_new(list->length);

	while(i<list->length) {
		chrom1 = newChromosome();
		chrom2 = newChromosome();
		chrom1 = (Chromosome *)(list-> data[i]);
		chrom2 = (Chromosome *)(list-> data[i+1]);
		for(j=firstPoint; j<chrom1-> colors-> length; j++) {
			aux = chrom1-> colors-> data[j];
			chrom1-> colors-> data[j] = chrom2-> colors-> data[j];
			chrom2-> colors-> data[j] = aux;
		}
		arraylist_append(cross,chrom1);
		arraylist_append(cross,chrom2);
		i = i + 2;
	}

	return cross;
}

ArrayList *crossoverTwoPoint(ArrayList *list, int firstPoint, int secondPoint){
	int i = 0,j; 
	ArrayListValue aux;
	Chromosome	*chrom1, *chrom2;
	ArrayList *cross = arraylist_new(list->length);

	while(i<list->length) {
		chrom1 = newChromosome();
		chrom2 = newChromosome();
		chrom1 = (Chromosome *)(list-> data[i]);
		chrom2 = (Chromosome *)(list-> data[i+1]);
		for(j=firstPoint; j<secondPoint; j++) {
			aux = chrom1-> colors-> data[j];
			chrom1-> colors-> data[j] = chrom2-> colors-> data[j];
			chrom2-> colors-> data[j] = aux;
		}
		arraylist_append(cross,chrom1);
		arraylist_append(cross,chrom2);
		i = i + 2;
	}

	return cross;
}

ArrayList *mutationKSwap(ArrayList *list, int k) {
	int i, j=0, pos1 = 0, pos2 = 0;
	Chromosome *chrom;
	ArrayListValue aux;
	ArrayList *cross = arraylist_new(list->length);

	for(i=0; i<list->length;i++) {
		chrom = newChromosome();	
		chrom = (Chromosome *)(list-> data[i]);
		while (j<k) {
			pos1 = rand()%chrom-> colors-> length;
			pos2 = rand()%chrom-> colors-> length;
			aux = chrom-> colors-> data[pos1];
			chrom-> colors-> data[pos1] = chrom-> colors-> data[pos2];
			chrom-> colors-> data[pos2] = aux;
			j++;
		}
		arraylist_append(cross,chrom);
	}
	return cross;
}

int countColors(ArrayList *list) {
	int i, j, k = 0, colors = 0;
	
	for (i=0; i<list-> length; i++) {
		for(j=0; j<list-> length; j++) {
			if (*(int *)(list-> data[j]) == (i+1) ) {
				k=1;
			}
		}
		if (k==1) {
			colors++;
			k=0;
		}
	}
	return colors;
}

Population *fixPopulation(Population *pop) {
	int i;
	Chromosome *chrom;
	
	// Se recalculan los colores
	for (i=0; i<pop-> chrom-> length; i++) {
		chrom = newChromosome();
		chrom = (Chromosome *)(pop-> chrom-> data[i]);
		chrom-> used = 0;
		pop-> chrom-> data[i] = chrom;
	}
	// Actualizamos el mejor
		chrom = newChromosome();
		chrom = findBetter(pop);
		pop-> better = chrom;
	
	return pop;
}

Population *makeFeasible(Population *pop, Graph *graph) {
	int i, j;
	double myRank = 0.0;
	Vertex *v;
	Chromosome *chrom;

	for (i=0; i<pop-> chrom-> length; i++){
		chrom = newChromosome();
		chrom = (Chromosome *)(pop-> chrom-> data[i]);
		// Agregamos los colores al grafo.
		for (j=0; j<chrom-> colors-> length; j++) {
			setColor(graph, graph-> vertex-> data[j], *(int *)(chrom-> colors-> data[j]));
		}
		// Aplicamos local search.
		apply_local_search(graph);
		// Compactamos el grafo.
		removeDeadColors(graph);
		myRank = (double)(penaltyCost(graph));
		for (j=0; j<chrom-> colors-> length; j++) {
			v = graph-> vertex-> data[j];
			*(int *)(chrom-> colors-> data[j]) = v-> color;
			chrom-> rank = myRank;
			pop-> chrom-> data[i] = (Chromosome *)(chrom);
		}
	}
	return pop;
}
